package main

import (
	"fmt"
	"strings"
)

// 双向链表
type DoublyLinkedList struct {
	head *Node
	tail *Node
}

// 链表头部添加元素
func (list *DoublyLinkedList) OfferFirst(e interface{}) {

	node := &Node{
		e:    e,
		prev: nil,
		next: nil,
	}

	head := list.head

	head.next.prev = node
	node.next = head.next
	node.prev = head
	head.next = node
}

// 链表尾部追加元素
func (list *DoublyLinkedList) OfferLast(e interface{}) {

	node := &Node{
		e:    e,
		prev: nil,
		next: nil,
	}

	tail := list.tail

	tail.prev.next = node
	node.prev = tail.prev
	node.next = tail
	tail.prev = node
}

// 获取头部元素
func (list *DoublyLinkedList) PeekFirst() (e interface{}) {

	head := list.head

	if head.next == list.tail {
		return nil
	}

	return head.next.e
}

// 获取尾部元素
func (list *DoublyLinkedList) PeekLast() (e interface{}) {

	tail := list.tail

	if tail.prev == list.head {
		return nil
	}

	return tail.prev.e
}

// 获取并移除头部元素
func (list *DoublyLinkedList) PollFirst() (r interface{}) {

	head := list.head

	if head.next == list.tail {
		return nil
	}

	node := head.next

	e := node.e

	head.next = node.next
	node.next.prev = head

	return e
}

// 获取并移除尾部元素
func (list *DoublyLinkedList) PollLast() (r interface{}) {

	tail := list.tail

	if tail.prev == list.head {
		return nil
	}

	node := tail.prev

	e := node.e

	tail.prev = node.prev
	node.prev.next = tail

	return e
}

// 覆盖String方法，格式化输出
func (list DoublyLinkedList) String() string {
	next := list.head.next
	// 空链表
	if next == list.tail {
		return "[]"
	} else {
		s := "["
		tmp := list.head.next
		for {
			s += fmt.Sprintf("%v, ", tmp.e)
			if tmp.next == list.tail {
				break
			}
			tmp = tmp.next
		}
		return strings.TrimRight(strings.TrimSpace(s), ",") + "]"
	}
}

// 获取正向迭代器
func (list *DoublyLinkedList) Iterate() *AscDoublyLinkedListIterator {
	return &AscDoublyLinkedListIterator{
		current: list.head,
		tail:    list.tail,
	}
}

// 获取反向迭代器
func (list *DoublyLinkedList) DescIterate() *DescDoublyLinkedListIterator {
	return &DescDoublyLinkedListIterator{
		current: list.tail,
		head:    list.head,
	}
}

// 表示一个链表节点
type Node struct {
	e    interface{}
	prev *Node
	next *Node
}

// 迭代器
type Iterator interface {
	HasNext() bool
	Next() interface{}
}

// 双向链表正向迭代器
type AscDoublyLinkedListIterator struct {
	current *Node
	tail    *Node
}

func (iter *AscDoublyLinkedListIterator) HasNext() bool {
	return iter.current.next != iter.tail
}

func (iter *AscDoublyLinkedListIterator) Next() interface{} {

	node := iter.current.next

	if node == iter.tail {
		return nil
	}

	e := node.e
	iter.current = node
	return e
}

// 双向链表反向迭代器
type DescDoublyLinkedListIterator struct {
	current *Node
	head    *Node
}

func (iter *DescDoublyLinkedListIterator) HasNext() bool {
	return iter.current.prev != iter.head
}

func (iter *DescDoublyLinkedListIterator) Next() interface{} {

	node := iter.current.prev

	if node == iter.head {
		return nil
	}

	e := node.e
	iter.current = node
	return e
}

// 示例元素结构体
type Student struct {
	id       int
	name     string
	nickname string
}

// 覆盖String方法，格式化输出
func (student *Student) String() string {
	return fmt.Sprintf("{id=%d, name=%s, nickname=%s}", student.id, student.name, student.nickname)
}

func main() {

	head := &Node{}
	tail := &Node{}

	head.next = tail
	tail.prev = head

	list := &DoublyLinkedList{
		head: head,
		tail: tail,
	}

	fmt.Println("list =", list)

	// 创建元素
	s1 := &Student{1, "宋江", "及时雨"}
	s2 := &Student{2, "卢俊义", "玉麒麟"}

	// 追加
	list.OfferLast(s1)
	list.OfferLast(s2)

	fmt.Println("list =", list)

	// 创建元素
	s3 := &Student{3, "吴用", "智多星"}
	s4 := &Student{14, "武松", "行者"}

	// 添加到链表的头部
	list.OfferFirst(s3)
	list.OfferFirst(s4)

	fmt.Println("list =", list)

	// 正向迭代
	iterate := list.Iterate()
	for {
		hasNext := iterate.HasNext()
		if !hasNext {
			break
		}
		e := iterate.Next()
		fmt.Printf("正向迭代元素: %v\n", e)
	}

	// 反向迭代
	descIterate := list.DescIterate()
	for {
		hasNext := descIterate.HasNext()
		if !hasNext {
			break
		}
		e := descIterate.Next()
		fmt.Printf("反向迭代元素: %v\n", e)
	}

	// 从头部获取元素
	first := list.PeekFirst()
	fmt.Printf("头部元素是: %v\n", first)

	// 从尾部获取元素
	last := list.PeekLast()
	fmt.Printf("尾部元素是: %v\n", last)

	// 从头部获取并移除元素
	for {
		pollFirst := list.PollFirst()
		if pollFirst == nil {
			break
		}
		fmt.Printf("移除头部元素: %v\n", pollFirst)
		fmt.Println("list =", list)
	}

	// 从尾部获取并移除元素
	for {
		pollLast := list.PollLast()
		if pollLast == nil {
			break
		}
		fmt.Printf("移除尾部元素: %v\n", pollLast)
	}

	fmt.Println("list =", list)
}
